package main

func MergeSort(nums []int) {
	l, r := 0, len(nums)-1
	MergeSortCore(nums, l, r)
}

func MergeSortCore(nums []int, l, r int) {
	if r <= l {
		return
	}
	// 划分
	mid := l + (r-l)/2
	MergeSortCore(nums, l, mid)
	MergeSortCore(nums, mid+1, r)

	// 合并两部分
	lefts := nums[l : mid+1]
	rights := nums[mid+1 : r+1]
	tmps := make([]int, r-l+1)
	index := 0
	i, j := 0, 0
	for i < len(lefts) && j < len(rights) {
		if lefts[i] <= rights[j] {
			tmps[index] = lefts[i]
			i++
		} else {
			tmps[index] = rights[j]
			j++
		}
		index++
	}
	for i < len(lefts) {
		tmps[index] = lefts[i]
		index++
		i++
	}
	for j < len(rights) {
		tmps[index] = rights[j]
		index++
		j++
	}
	for i := 0; i < len(tmps); i++ {
		nums[l+i] = tmps[i]
	}
}

func MergeSortV1(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	mid := len(nums) / 2
	lefts := MergeSortV1(nums[:mid])
	rights := MergeSortV1(nums[mid:])

	res := make([]int, 0)
	i, j := 0, 0
	for i < len(lefts) && j < len(rights) {
		if lefts[i] <= rights[j] {
			res = append(res, lefts[i])
			i++
		} else {
			res = append(res, rights[j])
			j++
		}
	}
	for i < len(lefts) {
		res = append(res, lefts[i])
		i++
	}
	for j < len(rights) {
		res = append(res, rights[j])
		j++
	}
	return res
}
